0539. 最小时间差【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 排序

1. 📝 题目描述

• leetcode

给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。

---

示例 1：

输入：timePoints = ["23:59","00:00"]
输出：1

示例 2：

输入：timePoints = ["00:00","23:59","00:00"]
输出：0

---

提示：

• 2 <= timePoints.length <= 2 * 10^4
• timePoints[i] 格式为 "HH:MM"

2. 🎯 s.1 - 排序

c

int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; }

int findMinDifference(char** timePoints, int timePointsSize) {
    int* mins = (int*)malloc(sizeof(int) * timePointsSize);
    for (int i = 0; i < timePointsSize; i++) {
        int h, m;
        sscanf(timePoints[i], "%d:%d", &h, &m);
        mins[i] = h * 60 + m;
    }
    qsort(mins, timePointsSize, sizeof(int), cmp);
    int res = 1440 - mins[timePointsSize - 1] + mins[0];
    for (int i = 1; i < timePointsSize; i++) {
        int diff = mins[i] - mins[i - 1];
        if (diff < res) res = diff;
    }
    free(mins);
    return res;
}

js

/**
 * @param {string[]} timePoints
 * @return {number}
 */
var findMinDifference = function (timePoints) {
  const mins = timePoints.map((t) => {
    const [h, m] = t.split(':')
    return parseInt(h) * 60 + parseInt(m)
  })
  mins.sort((a, b) => a - b)
  let res = 1440 - mins[mins.length - 1] + mins[0]
  for (let i = 1; i < mins.length; i++) {
    res = Math.min(res, mins[i] - mins[i - 1])
  }
  return res
}

py

class Solution:
    def findMinDifference(self, timePoints: List[str]) -> int:
        mins = sorted(int(t[:2]) * 60 + int(t[3:]) for t in timePoints)
        res = 1440 - mins[-1] + mins[0]
        for i in range(1, len(mins)):
            res = min(res, mins[i] - mins[i - 1])
        return res

• 时间复杂度：$O(n\log n)$
• 空间复杂度：$O(n)$

算法思路：

• 将时间转化为分钟数并排序
• 比较相邻时间差，同时考虑首尾跨午夜的差值